package com.such.kit.datastructure.graph.support;

import java.util.List;
import com.such.kit.datastructure.graph.bean.Vertex;

/**
 * @作者 SUCH
 * @日期 2016-9-27 下午3:35:23
 * @描述 图接口
 * @param <T>
 */
public interface Graph<T> {

	/**
	 * <p>方法名：getVertex</p>
	 * <p>描述：获取一个顶点</p>
	 * @param label 顶点标识
	 * @return 顶点
	 */
	public Vertex<T> getVertex(T label);

	/**
	 * <p>方法名：addVertex</p>
	 * <p>描述：添加一个顶点</p>
	 * @param label 顶点标识
	 * @return 顶点
	 */
	public Vertex<T> addVertex(T label);

	/**
	 * <p>方法名：removeVertex</p>
	 * <p>描述：删除一个顶点，并删除与其相关的前置顶点出度边、临接点入度边</p>
	 * @param label 顶点标识
	 * @return 顶点
	 */
	public Vertex<T> removeVertex(T label);

	/**
	 * <p>方法名：addEdge</p>
	 * <p>描述：添加一条边</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @return 是否添加成功
	 */
	public boolean addEdge(T begin, T end);

	/**
	 * <p>方法名：addEdge</p>
	 * <p>描述：添加一条边</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @param cost 花费
	 * @param checkLoop 检查环，检查出环则对执行的添加进行回滚
	 * @return 是否添加成功
	 */
	public boolean addEdge(T begin, T end, double cost, boolean checkLoop);

	/**
	 * <p>方法名：removeEdge</p>
	 * <p>描述：删除一条边</p>
	 * @param begin 开始点
	 * @param end 结束点
	 */
	public void removeEdge(T begin, T end);

	/**
	 * <p>方法名：hasEdge</p>
	 * <p>描述：检查顶点间是否存在边</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @return boolean
	 */
	public boolean hasEdge(T begin, T end);

	/**
	 * <p>方法名：getVertexSize</p>
	 * <p>描述：获取顶点数</p>
	 * @return 顶点数
	 */
	public int getVertexSize();

	/**
	 * <p>方法名：getEdgeSize</p>
	 * <p>描述：获取边数</p>
	 * @return 边数
	 */
	public int getEdgeSize();

	/**
	 * <p>方法名：isEmpty</p>
	 * <p>描述：顶点与边是否为空</p>
	 * @return boolean
	 */
	public boolean isEmpty();

	/**
	 * <p>方法名：clear</p>
	 * <p>描述：清空所有顶点与边</p>
	 */
	public void clear();

	/**
	 * <p>方法名：getDepthFirstTraversal</p>
	 * <p>描述：深度优先遍历</p>
	 * <p>
	 * 逻辑：<br>
	 * 1. 找到一个基点的临接点 N<br>
	 * 2. 以 N 作为新基点，找到一个临接点<br>
	 * 3. 递归 1、2，直到 N 找不到一个临接点<br>
	 * 4. 到此为止则完成了一次深度遍历<br>
	 * 5. 回溯到 N 的前置顶点，以其作为新基点<br>
	 * 6. 递归 1、2、3、4，直到完成所有深度遍历<br>
	 * </p>
	 * @param origin 基准顶点
	 * @return 遍历排序队列
	 */
	public List<T> getDepthFirstTraversal(T origin);

	/**
	 * <p>方法名：getBreadthFirstTraversal</p>
	 * <p>描述：广度优先遍历</p>
	 * <p>
	 * 逻辑：<br>
	 * 1. 找到一个基点的所有临接点并进行遍历<br>
	 * 2. 到此为止则完成了第 N 层广度遍历<br>
	 * 3. 取第 N 层中每个顶点的所有临接点并遍历<br>
	 * 4. 到此为止则完成了第 N + 1 层广度遍历<br>
	 * 5. 递归 3、4，直到最底层（找不到临接点）<br>
	 * </p>
	 * @param origin 基准顶点
	 * @return 遍历排序队列
	 */
	public List<T> getBreadthFirstTraversal(T origin);

	/**
	 * <p>方法名：getShortestPath</p>
	 * <p>描述：寻找两个指定顶点之间的最短路径</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @return 最短路径，返回值包括  begin、end
	 */
	public List<T> getShortestPath(T begin, T end);

	/**
	 * <p>方法名：getShortestPathLength</p>
	 * <p>描述：计算两个指定顶点之间的最短路径长度</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @return 最短路径长度，长度计算包括  begin、end
	 */
	public int getShortestPathLength(T begin, T end);

	/**
	 * <p>方法名：getCheapestPath</p>
	 * <p>描述：寻找两个指定顶点之间的费用最低路径</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @return 费用最低路径，返回值包括  begin、end
	 */
	public List<T> getCheapestPath(T begin, T end);

	/**
	 * <p>方法名：getCheapestPathCost</p>
	 * <p>描述：计算两个指定顶点之间的费用最低路径的费用总和</p>
	 * @param begin 开始点
	 * @param end 结束点
	 * @return 费用最低路径费用总和，费用计算包括  begin、end
	 */
	public double getCheapestPathCost(T begin, T end);

	/**
	 * <p>方法名：getTopologicalSort</p>
	 * <p>描述：执行有向图拓扑排序</p>
	 * <p>
	 * 逻辑：<br>
	 * 1. 找到所有入度为 0 顶点并遍历<br>
	 * 2. 完成遍历后将所有入度为 0 顶点的临接点入度减 1<br>
	 * 3. 递归 1、2，直到找不到入度为 0 顶点<br>
	 * 4. 检查是否还有未访问过的顶点<br>
	 * 5. 如果有则图中有顶点形成了环<br>
	 * 6. 如果没有则排序结束<br>
	 * </p>
	 * @return 排序结果
	 */
	public List<T> getTopologicalSort();

	/**
	 * <p>方法名：checkLoop</p>
	 * <p>描述：检查图中是否有顶点形成了环</p>
	 * @return boolean
	 */
	public boolean checkLoop();

	/**
	 * <p>方法名：getNextUnvisitedVertex</p>
	 * <p>描述：获取下一个未访问的顶点，并将其设置为已访问</p>
	 * @return 下一个未访问的顶点
	 */
	public Vertex<T> getNextUnvisitedVertex();

	/**
	 * <p>方法名：getUnvisitedVertices</p>
	 * <p>描述：获取未访问的顶点，并将其设置为已访问</p>
	 * @return 未访问的顶点
	 */
	public List<Vertex<T>> getUnvisitedVertices();

	/**
	 * <p>方法名：getNextInDegreeZeroVertex</p>
	 * <p>描述：获取下一个入度为 0  的顶点</p>
	 * @return 下一个入度为 0  的顶点
	 */
	public Vertex<T> getNextInDegreeZeroVertex();

	/**
	 * <p>方法名：getInDegreeZeroVertices</p>
	 * <p>描述：获取入度为 0  的顶点</p>
	 * @return 入度为 0  的顶点
	 */
	public List<Vertex<T>> getInDegreeZeroVertices();

	/**
	 * <p>方法名：getNextOutDegreeZeroVertex</p>
	 * <p>描述：获取下一个出度为 0  的顶点</p>
	 * @return 下一个出度为 0  的顶点
	 */
	public Vertex<T> getNextOutDegreeZeroVertex();

	/**
	 * <p>方法名：getOutDegreeZeroVertices</p>
	 * <p>描述：获取出度为 0  的顶点</p>
	 * @return 出度为 0  的顶点
	 */
	public List<Vertex<T>> getOutDegreeZeroVertices();

	/**
	 * <p>方法名：resetVertices</p>
	 * <p>描述：重置顶点算法实现辅助属性</p>
	 */
	public void resetVertices();

}
